package com.example.leetcode.trainingcamp.week4.Sunday;

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 *
 * <p>
 *
 * <p>示例 1:
 *
 * <p>输入: [7,5,6,4] 输出: 5
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer51 {

     // 暴力方法超时
    public int reversePairs(int[] nums) {
        int len = nums.length;
        int count = 0;
        for (int i = 0;i<len-1; i++){
            for (int j = i+1;j<len;j++){
                if (nums[i]>nums[j]){
                    count++;
                }
            }
        }
        return count;
    }

    // 使用归并排序，分组求解时间复杂度降低
    int sum = 0;
    public int reversePairs2(int[] nums){
        int[] temp = new int[nums.length];
        merge(nums,0,nums.length-1,temp);
        return sum;
    }

    public void merge(int[] nums,int low ,int high ,int[] temp){
        if (low>= high) return;
        int mid = (low + high) /2 ;
        merge(nums,low,mid,temp);
        merge(nums,mid+1,high,temp);
        mergeSort(nums,low,mid,high,temp);
    }

    public void mergeSort(int[] nums,int low,int middle,int high ,int[] temp){
        int i = low;
        int j = middle+1;
        int t = 0;
        while (i<= middle && j<= high){
            if (nums[i] <= nums[j]){
                temp[t++] = nums[i++];
            }else {
                sum += middle-i+1;
                temp[t++] = nums[j++];
            }
        }
        while (i<= middle){
            temp[t++] = nums[i++];
        }
        while (j<=high){
            temp[t++] = nums[j++];
        }
        t = 0;
        while (low<= high){
            nums[low++] = temp[t++];
        }
    }
}


class TestOffer51{
    public static void main(String[] args){
        int[] nums = {7,5,6,4};
        Offer51 o = new Offer51();
        System.out.println(o.reversePairs2(nums));
    }
}